Quantum computers promise substantial speedups for a host of important problems such as factoring, quantum simulation and optimization. Despite the fact that quantum properties have proven to be powerful resources for these algorithms, the foundation of many of these algorithms often reduces to classical reversible logic interspersed with Hadamard gates. This is especially true for algorithms, such as the quantum linear—systems algorithm that promise exponential speedups but rely strongly on implementing classical arithmetic. For practical inversion problems, hundreds of ancillary qubits may be needed to implement the arithmetic operations needed to perform the arithmetic reversibly. Typically quantum implementations of arithmetic operations use reversible circuits to implement rotations of a target system by using a “phase-kickback” approach described by Kitaev, “Quantum computations: algorithms and error correction,” Russian Math. Surveys 52:1191-1249 (1998), and Cleve et al. “Quantum algorithms revisited,” Proc. Royal Society of London (Series A) 454:339-354 (1997). Unfortunately, approaches based on classical arithmetic and phase-kickback require many qubits, and alternative approaches are needed.